package com.mlh.binarysearch;

/**
 * @author 缪林辉
 * @date 2024/8/29 21:35
 * @DESCRIPTION
 */
//给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
// 算法的时间复杂度应该为 O(log (m+n)) 。 达到这个时间复杂度 玩的数论 没必要
public class 寻找两个正序数组的中位数 {
    //合并两个有序数组，然后二分查找就完事  时间复杂度是O(m+n)
    public static double method1(int[] nums1, int[] nums2) {
        int p1=0,p2=0;
        int len1=nums1.length,len2= nums2.length;
        int []merge= new int[len1+len2];
        for (int i = 0; i < merge.length; i++) {
            if(p1>=len1||p2>=len2){
                if(p1<len1){
                    merge[i]=nums1[p1++];
                }else{
                    merge[i]=nums2[p2++];
                }
            }else{
                merge[i]=nums1[p1]>nums2[p2]?nums2[p2++]:nums1[p1++];
            }
        }
        if(merge.length%2==0){//奇偶分开写
            return (merge[(len1+len2)/2-1]+merge[(len1+len2)/2])/2.0;
        }else{
            return (merge[(len1+len2)/2]);
        }
    }

    public static void main(String[] args) {
        method1(new int[]{1,12,43,44,55},new int[]{3,4,44,66,111});
    }
}
